package com.xjj.prefix;

import java.util.HashMap;
import java.util.Map;

public class M0560SubarraySumEqualsK {

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 不加0会漏算每个到s(i)本身满足的数
        // 比如k=2时,1,1,1会少一个[1,1]的,1,1,1,-1会少2个[1,1],[1,1,1,-1]
        map.put(0, 1);
        int sum = 0;
        int result = 0;
        for (int value : nums) {
            // 前缀和
            sum += value;
            // 此时map存的是i-1个的前缀和,所以找到满足sum-k的所有前缀和(个数)即可
            result += map.getOrDefault(sum - k, 0);
            // 将i的前缀和也加进去
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return result;
    }

}
